package LeetCode;

public class LC_222_CountCompleteTreeNodes {

    public static void main(String[] args) {

    }

    static class Solution {
        int countNodes(TreeNode root) {
            if (root == null)
                return 0;
            else {
                int left = getLeftHeight(root);
                int right = getRightHeight(root);
                if (left == right)
                    return (1 << left) - 1;
                else {
                    return countNodes(root.right) + countNodes(root.left) + 1;
                }
            }
        }

        static int getRightHeight(TreeNode root) {
            int height = 0;
            while (root != null) {
                height++;
                root = root.left;
            }
            return height;
        }

        static int getLeftHeight(TreeNode root) {
            int height = 0;
            while (root != null) {
                height++;
                root = root.right;
            }
            return height;
        }

    }
}